package org.xiaoxin.leetcode.array;

import java.util.*;

/**
 * * 49. 字母异位词分组
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * <p>
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 *
 * @author xiaoxin
 */
public class _49_groupAnagrams {

    /**
     * 1. 遍历字符串数组，将每个字符串转换为字符数组，并排序
     * 2. 将排序后的字符数组转换为字符串，作为map的key
     * 3. 将原字符串添加到map的value中
     * 4. 返回map的value
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 解法二：使用字符计数作为key
     * 1. 遍历字符串数组，统计每个字符串中各字符的出现次数
     * 2. 将字符计数数组转换为字符串作为map的key
     * 3. 将原字符串添加到map的value中
     * 4. 返回map的value
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 统计每个字符的出现次数
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                int index = c - 'a';
                count[index]++;
            }

            // 将计数数组转换为字符串作为key
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }


    public static void main(String[] args) {
//        testGroupAnagrams1();
        testGroupAnagrams2();
    }

    private static void testGroupAnagrams1() {
        _49_groupAnagrams solution = new _49_groupAnagrams();

        // 示例 1
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result1 = solution.groupAnagrams(strs1);
        System.out.println("示例 1:");
        System.out.println("输入: " + Arrays.toString(strs1));
        System.out.println("输出: " + result1);
        System.out.println();

        // 示例 2
        String[] strs2 = {""};
        List<List<String>> result2 = solution.groupAnagrams(strs2);
        System.out.println("示例 2:");
        System.out.println("输入: " + Arrays.toString(strs2));
        System.out.println("输出: " + result2);
        System.out.println();

        // 示例 3
        String[] strs3 = {"a"};
        List<List<String>> result3 = solution.groupAnagrams(strs3);
        System.out.println("示例 3:");
        System.out.println("输入: " + Arrays.toString(strs3));
        System.out.println("输出: " + result3);
        System.out.println();
    }

    /**
     * 测试第二种解法
     */
    public static void testGroupAnagrams2() {
        _49_groupAnagrams solution = new _49_groupAnagrams();

        System.out.println("=== 测试第二种解法（字符计数） ===");

        // 示例 1
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result1 = solution.groupAnagrams2(strs1);
        System.out.println("示例 1:");
        System.out.println("输入: " + Arrays.toString(strs1));
        System.out.println("输出: " + result1);
        System.out.println();

        // 示例 2
        String[] strs2 = {""};
        List<List<String>> result2 = solution.groupAnagrams2(strs2);
        System.out.println("示例 2:");
        System.out.println("输入: " + Arrays.toString(strs2));
        System.out.println("输出: " + result2);
        System.out.println();

        // 示例 3
        String[] strs3 = {"a"};
        List<List<String>> result3 = solution.groupAnagrams2(strs3);
        System.out.println("示例 3:");
        System.out.println("输入: " + Arrays.toString(strs3));
        System.out.println("输出: " + result3);
        System.out.println();

        // 示例 4 - 更复杂的测试用例
        String[] strs4 = {"abc", "bca", "cab", "xyz", "zyx", "yxz"};
        List<List<String>> result4 = solution.groupAnagrams2(strs4);
        System.out.println("示例 4:");
        System.out.println("输入: " + Arrays.toString(strs4));
        System.out.println("输出: " + result4);
        System.out.println();
    }
}
